import java.lang.reflect.Array;
import java.util.Arrays;

public class Test13_1 {
    /**
     *
     * @param threshold 约束值
     * @param rows 行数
     * @param cols 列数
     * @return
     */
    public static int movingCount(int threshold, int rows, int cols){
        if(threshold< 0 ||rows < 1 ||cols < 1) return  0;
        //变量初始化
        boolean[] visited = new boolean[rows*cols];
        Arrays.fill(visited,false);
        return movingCountCore(threshold,rows,cols,0,0,visited);

    }

    /**
     *
     * @param threshold
     * @param rows
     * @param cols
     * @param currow 当前行
     * @param curcol 当前列
     * @param visited 是否被访问过
     * @return
     */
    public static int movingCountCore(int threshold, int rows, int cols,
                                      int currow, int curcol, boolean[] visited){
        int count = 0;
        if (check(threshold,rows,cols,currow,curcol,visited)){
            visited[currow*cols+curcol] = true;
            count = 1+movingCountCore(threshold,rows,cols,currow+1,curcol,visited) +
                    movingCountCore(threshold,rows,cols,currow,curcol+1,visited) +
                    movingCountCore(threshold,rows,cols,currow-1,curcol,visited) +
                    movingCountCore(threshold,rows,cols,currow,curcol-1,visited);
        }
        return count;
    }

    /**
     * 断机器人能否进入坐标为(row, col)的方格
     *
     * @param threshold 约束值
     * @param rows      方格的行数
     * @param cols      方格的列数
     * @param currow    当前处理的行号
     * @param curcol    当前处理的列号
     * @param visited   访问标记数组
     * @return 是否可以进入，true是，false否
     */
    public static boolean check(int threshold, int rows, int cols,
                                int currow, int curcol, boolean[] visited){
        return curcol >= 0 && curcol < cols && currow >= 0 && currow < rows && !visited[currow*cols+curcol]
                &&(getDigitSum(curcol) + getDigitSum(currow) <= threshold);
    }

    /**
     * 一个数字的数位之和
     * @param number 数字
     * @return 数字的数位之和
     */
    private static int getDigitSum(int number) {
        int result = 0;
        while (number > 0) {
            result += (number % 10);
            number /= 10;
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(movingCount(5, 10, 10) );
        System.out.println(movingCount(15, 20, 20) );
    }
}
